package code.D1217;

import java.util.Arrays;

/**
 * author : yeswater
 * date : 2023/12/18
 * 
 * 除自身以外数组的乘积
 * 
 */

public class T238 {
    // public int[] productExceptSelf(int[] nums) {
    //     int[] res = new int[nums.length];
    //     Arrays.fill(res, 1);
    //     for (int i = 0; i < nums.length; i++) {
    //         for (int j = 0; j < nums.length; j++) {
    //             if (i == j) {
    //                 continue;
    //             }
    //             res[i] *=  nums[j];
    //         }
    //     }
    //     return res;
    // }
    
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] s1 = new int[n + 2], s2 = new int[n + 2]; // 前缀和 后缀和
        s1[0] = s2[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            s1[i] = s1[i - 1] * nums[i - 1];
        }
        for (int i = n; i >= 1; i--) {
            s2[i] = s2[i + 1] * nums[i - 1];
        }
        int[] ans = new int[n];
        for (int i = 1; i <= n; i++) {
            ans[i - 1] = s1[i - 1] * s2[i + 1];
        }
        return ans;
    }
}
